1546A - AquaMoon and Two Arrays - CodeForces Solution


brute force greedy *800

Please click on ads to support us..

Python Code:

import sys

input = sys.stdin.readline
inf = float('inf')


def getInt():
    return int(input())


def getStr():
    return input().strip()


def getList(split=True):
    s = getStr()
    if split:
      s = s.split()
    return map(int, s)

t = getInt()


def solve():
    n = getInt()
    a = list(getList())
    b = list(getList())
    if sum(a) != sum(b):
      print(-1)
    else:
      res = []
      p = []
      q = []
      for i in range(n):
        diff = a[i] - b[i]
        if diff < 0 :
          q.extend([i+1] * -diff)
        elif diff > 0:
          p.extend([i+1] * diff )
      print(len(p))
      for i,j in zip(p, q):
        print(i,j)
                  
  

for _ in range(t):
    solve()

C++ Code:

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 1e6 + 10;
inline void solve() {
    int n, ans = 0, k = 0;
    
    scanf("%lld", &n);
    vector<int> a(n), b(n), c, d;
    c.clear(); d.clear();
    for(int i = 0; i < n; i++) cin>>a[i];
    for(int i = 0; i < n; i++) cin>>b[i];
    for(int i = 0; i < n; i++) {
        if(a[i] > b[i]) {
            for(int j = 1; j <= a[i] - b[i]; j++)
                c.push_back(i);
        }
        else if(a[i] < b[i]) {
            for(int j = 1; j <= b[i] - a[i]; j++)
                d.push_back(i);
        }
    }
    if(c.size() - d.size() != 0) cout << -1 << endl;
    else {
        cout << c.size() << endl;
        for(int i = 0; i < c.size(); i++) {
            cout << c[i] + 1 << " " << d[i] + 1 << endl;
        }
    }
    return ;
}
signed main() {
    int t; scanf("%lld", &t);
    while(t--) solve();
    return 0;
}
	   		 	   		 	 		 		 	 	  	 	


Comments

Submit
0 Comments
More Questions

1302. Deepest Leaves Sum
1209. Remove All Adjacent Duplicates in String II
994. Rotting Oranges
983. Minimum Cost For Tickets
973. K Closest Points to Origin
969. Pancake Sorting
967. Numbers With Same Consecutive Differences
957. Prison Cells After N Days
946. Validate Stack Sequences
921. Minimum Add to Make Parentheses Valid
881. Boats to Save People
497. Random Point in Non-overlapping Rectangles
528. Random Pick with Weight
470. Implement Rand10() Using Rand7()
866. Prime Palindrome
1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST